import java.util.*;

public class BinaryTree3 {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode N1 = new TreeNode(1);
        TreeNode N2 = new TreeNode(9);
        TreeNode N3 = new TreeNode(10);
        TreeNode N4 = new TreeNode(28);
        TreeNode N5 = new TreeNode(17);
        TreeNode N6 = new TreeNode(12);
        TreeNode N7 = new TreeNode(14);
        TreeNode N8 = new TreeNode(8);
        TreeNode N9 = new TreeNode(6);
        TreeNode N10 = new TreeNode(24);
        N1.left = N2;
        N1.right = N3;
        N2.left = N4;
        N2.right = N5;
        N3.left = N6;
        N3.right = N7;
        N4.left = N8;
        N5.right = N9;
        N9.left = N10;
        return N1;
    }

    //递归前序遍历：
    public void preOrder(TreeNode root){
        //根节点为空时的特殊条件：
        //但也是结束递归的条件：
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //非递归前序遍历：

    //递归中序遍历：
    public void inOrder(TreeNode root){
        //根节点为空时的特殊条件：
        //但也是结束递归的条件：
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //非递归中序遍历：

    //递归后序遍历：
    public void postOrder(TreeNode root){
        //根节点为空时的特殊条件：
        //但也是结束递归的条件：
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //非递归后序遍历：

    //二叉树根节点总数：
    //子问题思路：
    public int treeNodeSum(TreeNode root){
        if(root == null){
            return 0;
        }
        return treeNodeSum(root.left) + treeNodeSum(root.right) + 1;
    }

    //二叉树叶子节点数：
    //节点为空，返回0 ，不递归
    //节点为叶子节点，返回1，不递归
    //所以每一个能递归的节点，都不是叶子节点
    //每一个能递归的节点，返回的，是左右子树叶子节点数
    public int leafNode(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return leafNode(root.left) + leafNode(root.right);
    }

    //二叉树的高度：
    //节点为空，返回0，不递归
    //所以非空节点，递归，自己那层的高度+1，再＋上左右子树高度的最大值
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    //二叉树第 k 层的节点数
    public int kLevelNode(TreeNode root, int k){
        //节点为空，有两种情况：
        //1.到了 k 层，节点为空，返回 0
        //2. 还未到 k 层，节点为空，返回 0 ，不再递归
        if(root == null){
            return 0;
        }
        //节点不为空，并且在k == 1 的那层，也就是第 k 层时，返回1，不递归
        if(k == 1){
            return 1;
        }
        //还未到第 k 层时，需要递归，返回左右子树累计第 k 层的节点数
        return kLevelNode(root.left,k-1) + kLevelNode(root.right,k-1);
    }

    //检测 value 值是否存在
    public TreeNode valueExistOrNot(TreeNode root, int value){
        if(root == null){
            return null;
        }
        if(root.val == value){
            return root;
        }
        TreeNode left = valueExistOrNot(root.left,value);
        if(left != null){
            return left;
        }
        TreeNode right = valueExistOrNot(root.right,value);
        if(right != null){
            return right;
        }
        return null;
    }

    //层序遍历
    public void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.println(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

    //检查两个树是否相同
    public boolean isSameTree(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 != null || root1 != null && root2 == null){
            return false;
        }
        //到这里之后，两颗二叉树的对应节点都为空，或者 都不为空
        if(root1 == null && root2 == null){
            return true;
        }
        if(root1.val != root2.val){
            return false;
        }
        //节点的值相等之后，继续递归
        return isSameTree(root1.left,root2.left) && isSameTree(root1.right,root2.right);
    }

    //另一颗子树
    public boolean subTree(TreeNode root , TreeNode sub){
        //root 包含 sub，返回 true ，不再递归
        if(isSameTree(root,sub)){
            return true;
        }

        if(root == null && sub != null){
            return false;
        }

        return subTree(root.left,sub) || subTree(root.right,sub);
    }

    //翻转二叉树
    public TreeNode invertTree(TreeNode root){
        if(root == null){
            return null;
        }
        TreeNode cur = root.left;
        root.left = root.right;
        root.right = cur;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //判断一颗二叉树是否为平衡二叉树
    //
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        return getHeight1(root) >= 0;
    }
    //两颗子树的高度差比较
    public int getHeight1(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight1(root.left);
        if(leftHeight < 0){
            return -1;
        }
        int rightHeight = getHeight1(root.right);
        if(rightHeight < 0){
            return -1;
        }

        if(Math.abs(leftHeight - rightHeight) < 2){
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }else{
            return -1;
        }
    }

    //是否为对称二叉树
    public boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }
        return createChildTree(root.left,root.right);
    }

    public boolean createChildTree(TreeNode p , TreeNode q){
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        if(q == null && p == null){
            return true;
        }
        if(q.val != p.val){
            return false;
        }
        return createChildTree(p.left,q.right) && createChildTree(p.right,q.left);
    }

    //p 和 q 两个数值的最近公共祖先
    //q ≠ p ，并且所有节点的数值各不相同
    //递归的返回值其实有两种，要么是目标数值对应的节点，要么是公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root,int p ,int q){
        if(root == null){
            return null;
        }
        if(root.val == p || root.val == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null){
            return root;
        }else if(left != null){
            return left;
        }else if(right != null){
            return right;
        }else{
            return null;
        }
    }

    //公共祖先的方法二：
    private boolean getPath(TreeNode root, Stack<TreeNode> stack ,TreeNode key){
        if(root == null || key == null){
            return false;
        }
        stack.push(root);
        if(root.val == key.val){
            return true;
        }
        boolean left = getPath(root.left,stack,key);
        if(left){
            return true;
        }
        boolean right = getPath(root.right,stack,key);
        if(right){
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor1(TreeNode root ,TreeNode p , TreeNode q){
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,stack1,p);
        getPath(root,stack2,q);

        int size1 = stack1.size();
        int size2 = stack2.size();

        int quotient = Math.abs(size1 - size2);
        if(size1 > size2){
            while(quotient > 0){
                stack1.pop();
                quotient--;
            }
        }else{
            while(quotient > 0){
                stack2.pop();
                quotient--;
            }
        }

        TreeNode cur  = null;
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek()!=stack2.peek()){
                stack1.pop();
                stack2.pop();
            }else{
                return stack1.pop();

            }
        }
        return null;
    }

    //根据一棵树的前序遍历与中序遍历构造二叉树
    //完全没思路，后面多写几遍
    public int i = 0;
    public TreeNode preInOrderTree(int[] preOrder , int[] inOrder){
        return buildChildTree(preOrder,inOrder,0,preOrder.length - 1 );

    }
    public TreeNode buildChildTree(int[] preOrder , int[] inOrder,int inbegin,int inend){
        if(inbegin > inend){
            return null;
        }
        int val = preOrder[i];
        i++;
        TreeNode root = new TreeNode(val);
        int valIndex = findIndex(inOrder,val,inbegin,inend);
        root.left = buildChildTree(preOrder,inOrder,inbegin,valIndex - 1);
        root.right = buildChildTree(preOrder,inOrder,valIndex + 1 , inend);
        return root;
    }

    //这里的 begin 和 end 已经是下标了，所有一定得取等号！！
    private int findIndex(int[] inOrder,int key,int begin,int end){
        for (int j = begin; j <= end; j++) {
            if(inOrder[j] == key){
                return j;
            }
        }
        return -1;
    }

    public int k = 0;
    //根据一棵树的中序遍历及后序遍历创建一颗二叉树
    public TreeNode inPostOrderTree(int[] inOrder,int[] postOrder){
        k = postOrder.length - 1;
        return buildChildTree1(inOrder,postOrder,0,inOrder.length - 1);
    }

    public TreeNode buildChildTree1(int[] inOrder,int[] postOrder,int inbegin,int inend){
        if(inbegin > inend){
            return  null;
        }
        int val = postOrder[k];
        k--;
        TreeNode root = new TreeNode(val);
        int valIndex = findIndex(inOrder,val,inbegin,inend);
        root.right = buildChildTree1(inOrder,postOrder,valIndex + 1,inend);
        root.left = buildChildTree1(inOrder,postOrder,inbegin,valIndex - 1);
        return root;
    }

    //将二叉树转换成字符串
    public String tree2String(TreeNode root){
        if(root == null){
            return null;
        }
        StringBuffer stringBuffer = new StringBuffer();
        create2String(root,stringBuffer);
        return stringBuffer.toString();
    }

    private void create2String(TreeNode root , StringBuffer stringBuffer){
        stringBuffer.append(root.val);
        if(root.left != null){
            stringBuffer.append("(");
            create2String(root.left,stringBuffer);
            stringBuffer.append(")");
        }else{
            if(root.right != null){
                stringBuffer.append("()");
            }else{
                return ;
            }
        }
        if(root.right != null){
            stringBuffer.append("(");
            create2String(root.right,stringBuffer);
            stringBuffer.append(")");
        }else{
            if(root.left != null){
                stringBuffer.append(")");
            }else{
                return;
            }
        }
    }

    //二叉树的层序遍历
    public List<List<Integer>> levelOrder1(TreeNode root){
        List<List<Integer>> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            while(size > 0){
                TreeNode cur = queue.poll();
                temp.add(cur.val);
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            list.add(temp);
        }
        return list;
    }

    //根据前序遍历，空树已标出，来创建一棵二叉树，最后再以中序遍历输出
    //多组输入
    public  void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            String string = sc.nextLine();
            TreeNode root = createTree1(string);
            inOrder(root);
        }
    }

    public int j  = 0;
    public  TreeNode createTree1(String str){
        TreeNode root = null;

        char ch = str.charAt(j);
        if(ch != '#'){
            root = new TreeNode(ch);
            root.left = createTree1(str);
            root.right = createTree1(str);
            j++;
        }else{
            j++;
        }


        return root;
    }

}
